#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 234. 回文链表.py
@time: 2022/1/22 14:23
@desc: https://leetcode-cn.com/problems/palindrome-linked-list/
> 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

1. 先找到中点，翻转后半部分，一一对比, Ot(n), Os(1)
'''

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        def findMid(head):
            slow, fast = head, head
            while fast.next and fast.next.next:
                slow, fast = slow.next, fast.next.next
            return slow

        def reverse(head):
            pre, p = None, head
            while p:
                next = p.next
                p.next = pre
                pre = p
                p = next
            return pre

        if not head.next: return True
        if not head.next.next: return head.val==head.next.val
        # 找中点拆
        mid = findMid(head)
        l2 = mid.next
        mid.next = None
        # 反转
        l2 = reverse(l2)
        # 对比
        l1 = head
        while l1 and l2:
            if not l1.val == l2.val:
                return False
            l1, l2 = l1.next, l2.next
        return True

if __name__ == '__main__':
    # head = ListNode(1, next=ListNode(2))
    head = ListNode(1, next=ListNode(1, next=ListNode(2, next=ListNode(1))))
    res = Solution().isPalindrome(head)
    print(res)